\section*{Appendix}\label{Sec:Appendix}

\section{Proofs of Simplifying assumptions from Section~\ref{sec:simplify_input_graph}}

\begin{proof} [Proof of Lemma~\ref{lem:firstsimple}]
First, observe that $e\in T\setminus OPT$ can be removed without
changing the solution of algorithm~\ref{alg:shadow_algorithm} and
the optimal solution. So, we may assume that $T\subseteq OPT$. We
now show that we can replace an edge in $OPT\setminus T$ by two new
edges which will be in $OPT\cap T$. Suppose for some $t$ there
exists an edge $e_t\in OPT$ that is not in $T$. (That is, $e_t\in
M_t$.) Let $e_t=y_1y_2$ and
define $g_1, g_2, a_1, a_2, c_1, c_2$ as
in algorithm~\ref{alg:shadow_algorithm}
%
and define $p_1, q_1, p_2, q_2, \ldots, p_k, q_k=y_1$ and $y_k=d_j, b_j, d_{j-1}, b_{j-1}, \ldots, d_1, b_1$
as in algorithm~\ref{alg:shadow_algorithm} (when $e_t$ is processed).
Add two vertices $v_1$ and $v_2$ to $G$ and two edges $e^1=v_1y_1$
and $e^2=v_2y_2$.
%
For $i\in \{1, 2\}$, define $y_ig_i:=$shadow-edge$(y_1y_2, y_i)$ and
$g_ia_i$ to be an edge in $M_t$ that covers $g_i$. First, if the alternating paths were of length two, then define weight
$$w(e^1):=min\{\gamma(w(y_1y_2)), \gamma(w(y_1y_2)+w(g_2a_2))-w(y_2g_2)\}$$ and
$$w(e^2):=min\{\gamma(w(y_1y_2)), \gamma(w(y_1y_2)+w(g_1a_1))-w(y_1g_1)\}.$$ Observe that
if $e^1$ arrives immediately after $e_t$ then it will not be added
by the algorithm since $w(e^1)\leq \gamma w(y_1y_2)$ and
$w(e^1)+w(y_2g_2)\leq \gamma(w(y_1y_2)+w(g_2a_2))$. The same
argument holds for $e^2$. Observe that
$\gamma(w(y_1g_1)+w(y_2g_2))\leq w(y_1y_2)+w(g_1a_1)+w(g_2a_2)$
because the edge $y_1y_2$ (that is, $e_t$) just arrives and kills
$y_1g_1$ and $y_2g_2$. Therefore,
$$w(e^1)+w(e^2) \geq w(y_1y_2).$$ So, we may instead consider the
graph $G$ with two vertices and edges added and let the two edges
$e^1$, $e^2$ arrive immediately after $e_t$. We replace $e_t$ in
$OPT$ by $e^1$ and $e^2$. To extend to our algorithm when the
alternating path is longer, let the notation of $p_l,q_l,d_r,b_r$ be
as in algorithm~\ref{alg:shadow_algorithm}. We will now consider the
path $p_{l+1}, q_{l+1}, \ldots, d_{r+1}, b_{r+1}$ to define $w(e^1)$
and $w(e^2)$ accordingly. $w(e^1)$ will be defined as $\gamma$ times
the minimum gain over all possibilities in which $(y_1,y_2)$ is
added (within these alternating paths). Similarly $w(e^2)$ and the
proof above carries through by a simple extension. \qed
\end{proof}


\begin{proof} [Proof of Lemma~\ref{lem:opt_has_degree_one}]

Below we state the proof for Zelke's algorithm for simplicity, but it extends to our algorithm in just the same way. So here we prove that if $y_2\neq q_{k-1}$ and $y_1\neq d_{j-1}$ then one of the first two conditions must hold. In the notation again in the algorithm, $y_2= q_{k-1}$ and $y_1= d_{j-1}$ are the same conditions as $g_1y_2= $ shadow-edge($y_1g_1$,
$g_1$) and $g_2y_1= $ shadow-edge($y_2g_2$, $g_2$)

Suppose there exists an edge $y_1y_2\in OPT$ that does not satisfy
the last two conditions; i.e., $g_1y_2\neq $ shadow-edge($y_1g_1$,
$g_1$) and $g_2y_1\neq $ shadow-edge($y_2g_2$, $g_2$). Using the
idea similar to previous lemma, we show that we can replace $y_1y_2$
by two edges $v_1y_1$ and $v_2y_2$ where $v_1$ and $v_2$ are new
vertices, such that $w(v_1y_1)+w(v_2y_2)\geq w(uv)$.
%The rest details are similar the the previous lemma.

Since $y_1y_2\in OPT$, $y_1y_2$ is not added to the matching (by the
previous lemma). This means that $y_1g_1$ and $y_2g_2$ prevent
$y_1y_2$ from being added to the matching. (The same argument works
if there is only one edge that prevents $y_1y_2$.) We may assume
that $g_1\neq y_2$; otherwise, this is the multiple edge case which
can be solved by creating a new vertex $v_1$, add an edge $v_1y_1$
of weight of the same weight with $y_1y_2$ and use this edge as an
edge in $OPT$ instead.

Next, let $g_1a_1$ be the shadow-edge($y_1g_1, g_1$) and let
$a_1c_1$ be an edge in the current matching. Define $g_2a_2$ and
$a_2c_2$ similarly. Note that since the last two conditions are not
satisfied, $a_1\neq y_2$ and $a_2\neq y_1$.
%
Now, define $e^1$ and $e^2$ similar to the proof of previous lemma.
By the same argument, $e^1$ and $e^2$ are in $OPT$ and $T$ and
$w(e^1)+w(e^2)\geq w(y_1y_2)$. \qed
\end{proof}


\section{Details of Proof of Invariant~\ref{inv:main}(\ref{inv:charge_limit})}
\label{app:proof_charge_limit}
\begin{description}
  \item[Case 1] Note that $ch_\tau(uv)\leq \alpha
  w(uv)$ (by Invariant~\ref{inv:main}(\ref{inv:charge_limit})).
  By Inequality~\eqref{eqn:second}, $(\beta \gamma f_\tau(u)+\beta \gamma
  f_\tau(v)) w(uv)\geq \alpha w(uv)\geq ch_\tau(uv).$
  %
  \item[Case 2] Note that $ch_\tau(uv)\leq \beta w(uv)$
  (by invariant~\ref{inv:main}(\ref{inv:charge_limit})). Now use
  Inequality~\eqref{eqn:second}.
  %
  \item[Case 3] Note that $ch_\tau(uv)\leq \alpha
  w(uv)$ and $ch_\tau(u)\leq \gamma w(uv)$ (by invariant~\ref{inv:main}(\ref{inv:charge_limit})).
  \begin{description}
  \item[Case 3.1] $(\beta\gamma+1)f_\tau(u))w(e)+\alpha\gamma
  f_\tau(v)w(e) \geq (\alpha+\gamma)(f_\tau(u)+f_\tau(v))w(e)\geq
  (\alpha+\gamma) w(e)$ where the first inequality follows from
  Lemma~\ref{lem:alpha_beta_gamma_ineq} and the second inequality
  follows from Lemma~\ref{lem:charge_eating}.
  %
  \item[Case 3.2.1] Let $u_{k+1}, v_k, u_k, ... , v_1, u_1, v_0, v'_0, u'_1, v'_1,
   ..., u'_k, v'_k, u'_{k'+1}$ be the charging chain at time $\tau'$
   as in Algorithm~\ref{alg:move_charge}. The total charge that the
   algorithm removes (in the last step) is
   \begin{eqnarray}
   w(v_0v'_0) + \sum_{i=1}^k (ch_{\tau} +
   ch_\tau(u_i)+ch_\tau(v_i)) \nonumber\\
   \leq
   w(v_0v'_0) + \sum_{i=1}^k (\alpha + 0 + \gamma)w(u_iv_i) \label{eq:old_charge}
   \end{eqnarray} while the total new charge
   the algorithm adds is
   \begin{eqnarray}
   \sum_{i=1}^k \beta\gamma (f_\tau(u_i)+f_\tau(v_i))w(u_iv_i)+\sum_{i=1}^k
   \gamma w(v_iu_{i+1}).\label{eq_new_charge}
   \end{eqnarray}
   Since the optimal edge $v_0v'_0$ is not
   added, $w(v_0v'_0)+\sum_{i=1}^k w(u_iv_i) \leq \gamma\sum_{i=0}^k
   w(v_iu_{i+1}).$ Using, $w(v_0v'_0) \leq \gamma\sum_{i=0}^k
   w(v_iu_{i+1}) - \sum_{i=1}^k w(u_iv_i)$, \eqref{eq:old_charge} is
   at most $$\gamma\sum_{i=0}^k w(v_iu_{i+1})
   + \sum_{i=1}^k (\alpha + \gamma -1 )w(u_iv_i)$$ which is at most
   \eqref{eq_new_charge} by Inequality~\eqref{eqn:third}.
%
%
  \item[Case 3.2.2] Again, use Inequality~\eqref{eqn:third}.
  \end{description}
  \item[Case 4] Similar to Case 3.
\end{description}


\section{Proof of Invariant~\ref{inv:main}(\ref{inv:charge_limit})}%
\label{app:proof_of_inv} For any $t$ and $t'<t$, any $x\in V(G)\cup
E(G)$, any edge $uv\in M_{t'}$, and some value $c$, we say that
$ch_t(x)$ receives charge of amount $c$ from $uv$ at time $t'$ if we
move charge of amount $c$ from $ch_{t'}(uv)$, $ch_{t'}(u)$, and
$ch_{t'}(v)$ to $ch_t(x)$. (In other words, the procedure {\sc
Move-Charge}($uv$, $t'$) puts charge of amount $c$ on $ch_t(x)$
(using $ch_t(x)\oplus c$).)

Now, for any $t$, consider an edge $d=ij$ in $M_{t+1}$ that kills
two edges $d^1=ii'$ and $d^2=jj'$ in $M_t$. (The same argument works
when $d$ kills only one edge.)
%The following facts can be checked by looking
%at the {\sc Move-Charge} algorithm.
%
\begin{lemma}\hfill
\begin{enumerate}
\item $ch_{t+1}(d)$ receives charge at time $t$ only (and from $d^1$ and
$d^2$ only).
\item If $ch_{t+1}(d)$ receives charge more than $\beta\gamma
f_t(i)w(d^1)$ from $d^1$ or more than $\beta\gamma f_t(j)w(d^2)$
from $d^2$ then $ch_{t+1}(i)$ or $ch_{t+1}(j)$ receives no charge.
\item $ch_{t+1}(d)$ never receives charge more than $\alpha\gamma
(f_t(i)w(d^1)+f_t(j)w(d^2))$ in total.
\end{enumerate}
\end{lemma}
\begin{proof}
The first claim follows from an observation that the procedure {\sc
Move-Charge}($uv$, $\tau$) moves charge to no other edges besides
$ch_{\tau+1}(e^1)$ and $ch_{\tau+1}(e^2)$ where $e^1$ and $e^2$ are
as in the {\sc Move-Charge} algorithm.

For the second claim, observe that only Case~3.1 gives charge to
edge more than $\beta\gamma$ of the weight. In particular,
$ch_{t+1}(d)$ receives charge more than $\beta\gamma f_t(i)w(d^1)$
but at most $\alpha\gamma f_t(i)w(d^1)$ from $d^1$ only when $d^1$
is $e$ and $d$ is $e^2$ as in Case 3.1 of the {\sc Move-Charge}
algorithm.
%
This case happens only if either $ch_t(i)=ch_{t+1}(i)=0$ or
$ch_t(j)=ch_{t+1}(j)=0$ at the time the procedure {\sc
Move-Charge}($d^1, t$) is called. Moreover, $ch_{t+1}(i)$ and
$ch_{t+1}(j)$ receive no charge from $d^1$.
%
Therefore, $ch_t(i)=ch_{t+1}(i)=0$ or $ch_t(j)=ch_{t+1}(j)=0$ after
the procedure {\sc Move-Charge}($d^1, t$) finishes. If
$ch_t(i)=ch_{t+1}(i)=0$ then no charge will be added to
$ch_{t+1}(i)$ (since $ch_t(i)=0$). Similarly, if
$ch_t(j)=ch_{t+1}(j)=0$ then no charge will be added to
$ch_{t+1}(i)$. Therefore, the second claim follows.


The third is easy to check as every case give charge at most
$\alpha\gamma$ times the weight. \qed
%Now we prove the third claim. The only possibility that this claim
%will be violated is when $d$ is $e^1$, $d^1$ is $e$, and $i$ is $v$
%in Case 3.2.1 of the {\sc Move-Charge} procedure.
%
%We claim that the charge on $ch_{t+1}(i)$ must come from $d^2$. To
%see this, observe that the only other possibility is when the charge
%comes from $e_{t''}$ for some $t''<t$ (where Case 3.2.1 is applied
%when {\sc Move-Charge}($e_{t''}$, $t''$) is called). However, this
%possibility move charge to time $\tau'$ such that $e_{\tau'}\in
%OPT$. Clearly, $\tau'\neq t+1$ since the edge that arrives at time
%$t+1$ is $d$.
%
%When the charge on $ch_{t+1}(i)$ comes from $d^2$, it could be
%checked that this charge is at most $\alpha \gamma f_t(j) w(d^2)$.
%Therefore, the total charge is as claimed.
\end{proof}

Now we prove the invariant for the edge case. If $ch_{t+1}(i)$ or
$ch_{t+1}(j)$ receives some charge, $d$ receives charge at most
$\beta\gamma(f_t(i)w(d^1)+f_t(j)w(d^2))$ by the second claim. This
amount is at most $\beta w(d)$ by Lemma~\ref{lem:charge_eating}
(i.e., $f_t(u)w(e^1) + f_t(v)w(e^2) \leq w(e)/\gamma$).

If both $ch_{t+1}(i)$ and $ch_{t+1}(j)$ receive no charge, $d$
receives charge at most $\alpha\gamma(f_t(i)w(d^1)+f_t(j)w(d^2))$ by
the third claim. This amount is at most $\alpha w(d)$ by
Lemma~\ref{lem:charge_eating}.\\

%-----------------------

Next, we prove the invariant for the vertex case.
%
Observe that when {\sc Move-Charge}($uv$, $\tau$) is called, all
cases except Case~3.2 put charge at most $\gamma f_\tau(u) w(e)$ and
$\gamma f_\tau(v) w(e)$ on $ch_{\tau+1}(u)$ and $ch_{\tau+1}(u)$,
respectively. Therefore, if Case~3.2 is not used when {\sc
Move-Charge}($d^1$, $\tau$) and {\sc Move-Charge}($d^2$, $\tau$) are
called, then $u$ and $v$ receive charge at most $w(d)$ and thus the
invariant is satisfied.

Now, suppose that Case~3.2.2 is used either for {\sc
Move-Charge}($d^1$, $\tau$) and {\sc Move-Charge}($d^2$, $\tau$) but
Case~3.2.1 is never used, then each vertex receive charge at most
$w(d)$ (from other cases) \textit{plus} $w(d)/\gamma$ (by
Case~3.2.1). This is at most $\gamma w(e)$ and so the invariant is
still satisfied.

Now we consider when Case~3.2.1 is used. In particular, when $d$ is
in the charging chain at time $\tau+1$. Assume without loss of
generality that the chain starts from the optimal edge and reaches
$i$ before $j$. This means that the chain will continue at $d^2$ if
it satisfied the conditions listed in the chain construction. By the
way we move charge in claim 3.2.1, $ch_{\tau+1}(i)$ becomes $\gamma
w(d)$. We note that $ch_{\tau+1}(i)$ gets charge $\gamma w(d)$ from
Case 3.2.1 only once since this case only applies to edges at time
$\tau'<\tau$ holding charge on $i$ but now all the charge is at $i$
at time $\tau$. Next, observe that if Case 3.2.2 is not used for
{\sc Move-Charge}($d^2$, $\tau$) then no additional charge will be
given to $ch_{\tau+1}(u)$. In this case, the invariant is satisfied.
It is then left to consider when Case 3.2.2 is used for {\sc
Move-Charge}($d^2$, $\tau$). In particular, when $d$ is $e^2$ and
$d_2$ is $e$ in the Case 3.2.2 explained in
Algorithm~\ref{alg:move_charge}. We show that this is impossible.

Note that if $d^2$ is also in the chain then the Case 3.2.2 will be
used for {\sc Move-Charge}($d^2$, $\tau$) instead of Case 3.2.1 and
so we are done. It is thus left the check when the chain ends at
$d$. Now, the chain could stop in 2 ways. The first way is when
$ch_{\tau}(j')=0$. The second way is when $d^2$ creates a loop. We
show that in this case we also have $ch_{\tau}(j')=0$.

To see this, first observe that edges in the path must be killed in
order; i.e., an edge that is closest to the optimal edges must be
killed first the follow by the next edge. (This is because the
killer of the next edge will stay from time it kills that edge. So,
if the previous edge is killed later, both edges (the previous edge
and the killer of the next edge) will appear at the same time.
However, these two edges share the same vertex.)

Now, $d^2$ could make a loop in two ways. First, it may be incident
to an edge in the chain an its shadow edge, say $e$ and $e'$,
respectively. In that case, it can be shown by the previous claim
that $d^2$ and $e'$ must be killed at the same time. However, this
is impossible since $d^2$ and $e'$ share a vertex. Second, it may be
incident to a shadow edge and the next edge in the chain, say $e$
and $e'$. In this case, since $e$ moves its charge to
$ch_{tau+1}(j)$ (where $j$ is is the vertex shared by $e$ and
$d^2$), $ch_{\tau}(j')=0$ as claimed.


When $ch_{\tau}(j')=0$, the mentioned Case 3.2.2 (when $d$ is $e^2$
and $d_2$ is $e$ in the Case 3.2.2 explained in
Algorithm~\ref{alg:move_charge}) will not be used since there must
be charge on $j'$ (which is $u$ in Algorithm~\ref{alg:move_charge}.
We thus show that Case 3.2.1 and 3.2.2 could not be used together
and thus finish the proof of the invariant.

%
%Let $u_{k+1}, v_k, u_k, ... , v_1, u_1, v_0, v'_0, u'_1, v'_1,...,
%u'_k, v'_k, u'_{k'+1}$, for some $k$ and $k'$ be such charging chain
%containing $d$ and  where $v_0v'_0=e_{\tau'}$ and for all $1<i\leq
%k$, $u_iv_i$ = shadow-edge($v_{i-1}u_i, u_i$) and $u'_iv'_i$ =
%shadow-edge($v'_{i-1}u'_i, u'_i$).
%
%\begin{lemma}
%For any edge $uv$ in the charging chain at time $\tau+1$ such that
%$u$ is closer to the optimal edge than $v$, if shadow-edge($uv$,
%$v$) exists, say $vz$, and $ch_{\tau'}(v)>0$ (where $\tau'$ is the
%time $vz$ is killed by $uv$) then either
%
%there is an edge in the matching covering $z$ or $ch_{\tau+1}(z)=0$.
%\end{lemma}
%\begin{proof}
%Recall that the chain will be stop when
%
%
% \qed
%\end{proof}



%Consider again an edge $ij\in M_{t+1}$ for any $t$. It can be
%checked that $ch_{t+1}(i)$ receives charge from at most two sources.
%The first source is an edge $ii'\in M_t$ killed by $ij$. The charge
%from this source is at most $f_t(i)w(ii')$. There are two
%possibilities for the second source.
%\begin{enumerate}
%\item The second source is an optimal edge that is prevented by $ij$.
%(I.e., an edge $e^{t'}\in OPT$ for some $t'\geq t+1$ such that
%$ij\in \bigcap_{t''=t+1}^{t'} M_{t''}$.) In this case, $ch_{t+1}(i)$
%receives charge at most $\gamma w(ij)$ and receives no charge from
%the first source.
%\item The second source is $ch_{t'}(i)$ for some $t'\leq t$. I.e., when
%the charge on an edge $ii'\in M_{t'}$ with $ch_{t'}(i)>0$ is being
%cleared by the charging scheme, some charge is put on $ch_{t+1}(i)$.
%\end{enumerate}
%
%Now we show that $ch_{t+1}(i)$ receives charge at most once from
%each of these sources. It is easy to see that there is a unique
%first source. To see that there is a unique second source, first
%note that two possibilities cannot happen together because of
%invariant~\ref{inv:main}(\ref{inv:unique_time}). Now, it is easy to
%see that the first possibility can happen only once as there is a
%unique edge in OPT that is incident to $v$. Next, since the second
%possibility can happen only when $ch_{t'}(i)>0$ and once it happens
%$ch_{t+1}(v)>0$, this possibility can also happen only once.
